Validate Stack Sequences(946)

发表于 | 分类于 | 浏览 次

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

1
2
3
4
5
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

1
2
3
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

题意是说，给定一个入栈序列和一个可能的出栈序列，问在给定的入栈序列下能否得到出栈序列。如果能返回true，否则返回false。

此题的解决是模拟。模拟入栈入栈并出栈的问题，尽量得到和给定的出栈序列一致的出栈序列。如例1，首先为了得到第一个出栈的是4，则必须将[1,2,3,4]入栈，然后将4出栈，则从栈底到栈顶的元素分别为[1,2,3]。第二步，为了得到出栈序列中的第二位5，必须将5入栈，然后将5出栈，得到出栈序列中的第二位，此时，栈中栈底到栈顶的各元素分别为[1,2,3]。第三步为了得到3，直接将栈顶元素出栈即可。第四步和第五步同第三步。

对于例2，同样，第一步为了得到出栈序列中的4，将1,2,3,4依次入栈，并将4出栈，得到出栈序列中的第一位，此时栈底到栈顶的各元素为[1,2,3]。第二步，为了得到出栈序列中的第二位3，将此时的栈顶元素3直接出栈即可。第三步，为了得到5，将5入栈，继而出栈，得到出栈序列[4,3,5]。第四步，需要得到出栈序列中的第四位1，每一步当我们希望得到出栈序列中的下一位时，我们有两个选择，要么这一位还未入栈，如第一步中的4，对于这种情况，我们需要将后续元素入栈，另一种情况是，这一位就是栈顶元素，如第二步中的3。此时，所有入栈序列中的元素都已经入栈，那么只有一种可能了，那就是出栈序列中的下一位就是栈顶元素。但是，通过比较出栈序列中的下一位和栈顶元素可知，栈顶元素不是出栈序列中的下一位，因此，此出栈序列无法由入栈序列得到，返回false。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int k = 0;
        for(int i=0;i<popped.size();i++){
            while(k < pushed.size() && (st.empty() || st.top()!=popped[i])){
                st.push(pushed[k++]);
            }
            if(st.top()==popped[i]){
                st.pop();
            }else{
                return false;
            }
        }
        return true;
    }
};